package com.zhugang.week09;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @program algorithms
 * @description: graph2
 * @author: chanzhugang
 * @create: 2022/08/22 11:39
 */
public class Graph2 {

    /**
     * 无向无权图：邻接表
     */
    // 顶点个数
    private int v;
    // 邻接表：数组类型是LinkedList
    private LinkedList<Integer> adj[];

    public Graph2(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {
        // 无向图一条边存两次
        adj[s].add(t);
        adj[t].add(s);
    }

    /**
     * 广度优先搜索：支持打印出从s到t的路径
     * queue + boolean[]
     *
     * @param s
     * @param t
     * @return
     */
    public void bfs_simple(int s, int t) {
        boolean[] visited = new boolean[v];
        // 队列实现
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;

        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }

        while (!queue.isEmpty()) {
            int p = queue.poll();
            if (p == t) {
                print(prev, s, t);
                return;
            }
            for (int i = 0; i < adj[p].size(); i++) {
                // 遍历链表中的节点
                int q = adj[p].get(i);
                if (!visited[q]) {
                    // 记录的是q的前驱节点p，节点是从哪个节点扩展出来的
                    prev[q] = p;
                    visited[q] = true;
                    queue.add(q);
                }
            }
        }
    }

    /**
     * 深度优先搜索
     *
     * @param s
     * @param t
     * @return
     */
    private boolean found = false;

    public void dfs_simple(int s, int t) {
        boolean[] visited = new boolean[v];
        int[] prev = new int[v];
        for (int i = 0; i < v; i++) {
            prev[i] = -1;
        }
        dfs_simple_r(s, t, visited, prev);
        print(prev, s, t);
    }

    private void dfs_simple_r(int s, int t, boolean[] visited, int[] prev) {
        if (found) return;
        visited[s] = true;
        if (s == t) {
            found = true;
            return;
        }
        for (int i = 0; i < adj[s].size(); i++) {
            int q = adj[s].get(i);
            if (!visited[q]) {
                // q的前驱节点是s
                prev[q] = s;
                dfs_simple_r(q, t, visited, prev);
            }
        }
    }


    /**
     * DFS: 支持打印出从s到t的路径
     * 类似回溯理解
     *
     * @param s
     * @param t
     * @return
     */
    private boolean[] visited = new boolean[v];
    private List<Integer> resultPath = new ArrayList<>();

    public List<Integer> dfs(int s, int t) {
        //回溯模版写法
        dfs_r(s, t, new ArrayList<>());
        return resultPath;
    }

    private void dfs_r(int s, int t, List<Integer> path) {
        if (s == t) {
            resultPath = new ArrayList<>(path);
            return;
        }
        visited[s] = true;
        path.add(s);
        for (int i = 0; i < adj[s].size(); i++) {
            int q = adj[s].get(i);
            if (!visited[q]) {
                dfs_r(q, t, path);
            }
        }
        // 回退后删掉节点
        path.remove(path.size() - 1);
    }

    /**
     * 递归打印s-t的路径
     *
     * @param prev
     * @param s
     * @param t
     */
    private void print(int[] prev, int s, int t) {
        // 类似逆序打印链表： 因为记录的是q的前驱节点p
        if (prev[t] != -1 && t != s) {
            print(prev, s, prev[t]);
        }
        System.out.println(t + " ");
    }
}